Computational Complexity ------------------------ [(Up)](../../README.md#topics) | _See also: [Theory of Computation](../Theory%20of%20Computation/README.md#theory-of-computation)_ - - - - ### Web resources [Computability and Complexity (Stanford Encyclopedia of Philosophy)](https://plato.stanford.edu/entries/computability/) ★★★ [Descriptive Complexity](https://people.cs.umass.edu/~immerman/descriptive_complexity.html) ★★ [hierarchy theorems - Examples of collapsing hierarchies - Theoretical Computer Science Stack Exchange](https://cstheory.stackexchange.com/questions/47333/examples-of-collapsing-hierarchies) ★ [lower bounds - Law of the Excluded Middle in complexity theory - Theoretical Computer Science Stack Exchange](https://cstheory.stackexchange.com/questions/53305/law-of-the-excluded-middle-in-complexity-theory) ★ [Galactic algorithm - Wikipedia](https://en.wikipedia.org/wiki/Galactic_algorithm) [Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science](http://theoryofcomputing.org/) ★ [💭](commentary/Chris%20Pressey.md#theory-of-computing-an-open-access-electronic-journal-in-theoretical-computer-science) ### P, NP, and beyond [turing machines - Do I need to consider instance restrictions when showing a language is in P? - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/105692/do-i-need-to-consider-instance-restrictions-when-showing-a-language-is-in-p) ★ [Cobham\'s thesis - Wikipedia](https://en.wikipedia.org/wiki/Cobham's_thesis) [gr.group theory - Are there any computational problems in groups that are harder than P? - MathOverflow](https://mathoverflow.net/questions/321547/are-there-any-computational-problems-in-groups-that-are-harder-than-p) ★ [cc.complexity theory - Subexponentially solvable hard graph problems - Theoretical Computer Science](https://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems) [cc.complexity theory - A category of NP-complete problems? - Theoretical Computer Science](https://cstheory.stackexchange.com/questions/3074/a-category-of-np-complete-problems) ### P versus NP [P-versus-NP page](https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm) ★ [Computational Complexity: So You Think You Settled P verus NP](http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html) ★★★ [About P=NP and SAT « Gödel's Lost Letter and P=NP](http://rjlipton.wordpress.com/about/) ★ ### PSPACE [Computational Complexity: A Simple PSPACE-Complete Problem](https://blog.computationalcomplexity.org/2012/11/a-simple-pspace-complete-problem.html) ★★★ ### PR [computability theory - Inverse Ackermann - primitive recursive or not? - MathOverflow](https://mathoverflow.net/questions/76037/inverse-ackermann-primitive-recursive-or-not) ★ [Between mu- and primitive recursion - MathOverflow](http://mathoverflow.net/questions/46350/between-mu-and-primitive-recursion) ★ [computability theory - Is the collection of primitive recursive functions a lower set in the poset of computable functions? - MathOverflow](https://mathoverflow.net/questions/364494/is-the-collection-of-primitive-recursive-functions-a-lower-set-in-the-poset-of-c) ### Papers Why Philosophers Should Care About Computational Complexity (online @ [www.scottaaronson.com](https://www.scottaaronson.com/papers/philos.pdf), [arxiv.org](https://arxiv.org/abs/1108.1791v3)) ★★★ [💭](commentary/Chris%20Pressey.md#why-philosophers-should-care-about-computational-complexity) Protein folding is NP-hard (online @ [www.gwern.net](https://www.gwern.net/docs/1993-fraenkel.pdf)) ★ Complexity Hierarchies Beyond Elementary (online @ [arxiv.org](https://arxiv.org/abs/1312.5686)) [💭](commentary/Chris%20Pressey.md#complexity-hierarchies-beyond-elementary) The Typed Lambda Calculus is not Elementary Recursive (online @ [www.cs.cornell.edu](https://www.cs.cornell.edu/courses/cs6110/2012sp/Statman-typed-lambda-calculus.pdf)) ★ Pure vs Impure Lisp (online @ [dl.acm.org](https://dl.acm.org/doi/pdf/10.1145/244795.244798)) _(in [Modal Logic](../Modal%20Logic/README.md#modal-logic))_ Topology, Connectedness, and Modal Logic (online @ [www.dcs.bbk.ac.uk](https://www.dcs.bbk.ac.uk/~roman/papers/aiml-08-55.pdf), [web.archive.org](https://web.archive.org/web/20240413205519/https://www.dcs.bbk.ac.uk/~michael/AiML-08.pdf)) ★ [💭](commentary/Chris%20Pressey.md#topology-connectedness-and-modal-logic) _(in [Model Checking](../Model%20Checking/README.md#model-checking))_ [Model Checking CTL is Almost Always Inherently Sequential](https://arxiv.org/abs/1103.4990) [💭](commentary/Chris%20Pressey.md#model-checking-ctl-is-almost-always-inherently-sequential) ### Books Computers and Tractability (borrow @ [archive.org](https://archive.org/details/computersintract0000gare)) 🏛️ [💭](commentary/Chris%20Pressey.md#computers-and-tractability) Computational Complexity (Papadimitriou) (borrow with print disabilities @ [archive.org](https://archive.org/details/computationalcom0000papa)) ★ [💭](commentary/Chris%20Pressey.md#computational-complexity-papadimitriou) Computational Complexity (Wagner and Wechsung) (borrow @ [archive.org](https://archive.org/details/computationalcom0000wagn)) [💭](commentary/Chris%20Pressey.md#computational-complexity-wagner-and-wechsung) _(in [Linguistics](../Linguistics/README.md#linguistics))_ The Language Complexity Game (borrow @ [archive.org](https://archive.org/details/languagecomplexi00rist)) ★ [💭](commentary/Chris%20Pressey.md#the-language-complexity-game)